package com.yang.Offer;

import java.util.List;

public class Offer32_3 {
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
/*请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印
第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。*/
class Offer32_3Solution {
//    public List<List<Integer>> levelOrder(TreeNode root) {
//        if(root == null){
//            return new ArrayList();
//        }
//        List<List<Integer>> numsList = new ArrayList();
//        Deque<TreeNode> queue = new LinkedList<>();
//        queue.offer(root);
//        boolean isTurn = true;
//        // 使用双端队列方法
//        while(!queue.isEmpty()){
//            int len = queue.size();
//            List<Integer> nums = new ArrayList();
//            for(int i = 0; i< len; i++){
//                if(isTurn){// 正常队列 头出尾进
//                    TreeNode node = queue.removeFirst();
//                    if (node.left != null){
//                        queue.addLast(node.left);
//                    }
//                    if (node.right != null){
//                        queue.addLast(node.right);
//                    }
//                    nums.add(node.val);
//                }
//                else{// 头进尾出 头进也是按照相反的顺序进，因为偶数数列是头出 这样偶数列取出来的时候就是正常的数据  而奇数列我们从尾巴取东西正好相反
//                    TreeNode node = queue.removeLast();
//                    if (node.right != null){
//                        queue.addFirst(node.right);
//                    }
//                    if (node.left != null){
//                        queue.addFirst(node.left);
//                    }
//                    nums.add(node.val);
//                }
//            }
//            isTurn = !isTurn;
//            numsList.add(nums);
//        }
//        return numsList;
//    }
}
